//给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。 
//
// 例如: 
//
// 
//输入:
//[1,2,3]
//
//输出:
//2
//
//说明：
//只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： 
//
//[1,2,3]  =>  [2,2,3]  =>  [2,2,2]
// 
// Related Topics 数组 数学 排序 
// 👍 148 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class MinimumMovesToEqualArrayElementsIi {
    public static void main(String[] args) {
        Solution solution = new MinimumMovesToEqualArrayElementsIi().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 排序之后找中位数
     * 是所有数据的中位数
     * 如果数字的个数是奇数
     * [0,1,2,6,8]
     * 那么[0,8]这两个数在其范围内任意选一个数，两个元素移动的和都是8
     * [1,6]同理移动的长度都是5，所以需要让中间的数移动的次数最少，所以选择2位目标点
     *
     * 偶数个数的话[0,2,6,8]      2和6任选一个都行
     *
     * 使用双指针从遍历的数组两头开始向中间遍历，两数字差就是当前两数移动距离，最后如果能剩下的话就是中位数
     *
     */
    class Solution {
        public int minMoves2(int[] nums) {
            Arrays.sort(nums);
            int res = 0;
            int i = 0;
            int j = nums.length-1;
            while (i<j){//使用双指针的话剩下的就是中位数了
                res += nums[j--]-nums[i++];
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}